package com.coderside.fragment.arithmetic;

public class InsertSort {

	private static long count;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] arr = createList();
		long a = System.nanoTime();
		insertSort(arr);
		long b = System.nanoTime();
		System.out.println(b - a);
		System.out.println(count);
	}
	private static int[] createList() {
		int i = 0;
		int size = 5000;
		int[] arr = new int[size];
		while (i < size) {
			arr[i] = (int) (Math.random() * size);
			i++;
		}
		return arr;
	}
	private static void insertSort(int[] list) {
		int len = list.length;
		for (int i = 0; i < len; i++) {
			for (int j = i; j > 0; j--) {
				count++;
				int e1 = list[j - 1];
				int e2 = list[j];
				if (e1 > e2) {
					list[j] = e1;
					list[j - 1] = e2;
				} else {
					break;
				}
			}
		}
	}

}
